package cn.edu.jxau.test;

import java.util.Arrays;

/**
 * 求KendallTau距离
 * 
 * @author 付大石
 */
public class Main {

    public static void main(String[] args) {

        System.out.println(distance(new int[] { 0, 3, 1, 6, 2, 5, 4 }, new int[] { 1, 0, 3, 6, 4, 2, 5 }));
    }

    private static int distance(int[] arr1, int[] arr2) {

        // 参数校验 //
        if (arr1.length != arr2.length) {
            throw new IllegalArgumentException("两个数组长度不同");
        }
        int len = arr1.length;
        int n = arr1.length;

        int[] ainv = new int[n];
        for (int i = 0; i < n; i++)
            ainv[arr1[i]] = i;
        System.out.println(Arrays.toString(ainv));
        Integer[] bnew = new Integer[n];
        for (int i = 0; i < n; i++)
            bnew[i] = ainv[arr2[i]];
        System.out.println(Arrays.toString(bnew));
        return countInversions(bnew);
    }

    /**
     * 利用稳定的归并排序求一个有序数组中逆序对的数量
     * 
     * @param arr
     * @param id
     */
    private static <T extends Comparable<T>> int countInversions(T[] arr) {

        T[] aux = (T[]) new Comparable[arr.length];
        return countInversions(arr, aux, 0, arr.length - 1);
    }

    private static <T extends Comparable<T>> int countInversions(T[] arr, T[] aux, int low, int high) {

        int count = 0;
        if (high <= low) {
            return count;
        }
        int mid = low + ((high - low) >> 1);
        count += countInversions(arr, aux, low, mid);
        count += countInversions(arr, aux, mid + 1, high);
        count += merge(arr, aux, low, mid, high);
        return count;
    }

    private static <T extends Comparable<T>> int merge(T[] arr, T[] aux, int low, int mid, int high) {

        int count = 0;
        int i = low;
        int j = mid + 1;
        for (int k = low; k <= high; k++) {
            aux[k] = arr[k];
        }

        int k = low;
        while (i <= mid && j <= high) {
            if (aux[i].compareTo(aux[j]) <= 0) {
                arr[k++] = aux[i++];
            } else if (aux[i].compareTo(aux[j]) > 0) {
                arr[k++] = aux[j++];
                count += mid - i + 1;
            }
        }
        while (i <= mid) {
            arr[k++] = aux[i++];
        }
        while (j <= high) {
            arr[k++] = aux[j++];
        }
        return count;
    }
}
